Field of the Invention
The present invention is related to multiprocessor computer systems, and more particularly to routing control in packet traffic within a multiprocessor computer system.
Background Information
In multiprocessor computer systems, there are often multiple paths for the transfer of data between compute nodes. Messages to be sent from one node to another node within the system must, oftentimes, be told the particular path to traverse. The primary mechanisms for providing routing information are source routing, distributed table-driven routing and algorithmic routing.
Source routing is used in the Sandia ASCI Red system. In source routing, a lookup table at the source node provides routing information for the entire path of a packet through the network to its destination. The routing information is carried along with the packet and used to select router output ports at each hop. Source routing provides flexibility in selecting the route, but is less able to handle problems that may come up as the packet traverses the network.
Distributed table-driven routing is used in the Cray T3E, the Cray X1, the Cray XT3, the Mellanox IB routers and the SGI Altix. In distributed table-driven routing, a lookup table is used at each hop along the path (generally indexed by the destination node number) to determine the output port of the current router.
Distributed table-driven routing can require large routing tables, especially as the number of nodes in the system increase.
In one variation of distributed table-driven routing, the routing table specifies the output port of the next router, in a pipelined fashion. By carrying information for the selected egress port of the next router, the packet can arbitrate for the selected egress port at the time it enters a router, rather than waiting to select the egress port and then arbitrate for it. Such an approach is described in U.S. Pat. No. 5,721,819, issued Feb. 24, 1998 to Galles et al.
Galles' approach limits the number of table entries by splitting the routing table into a local routing table and a remote routing table. The local routing table is used when the packet approaches its destination to route the packet to its destination node. The remote routing table is used to push the packet in the general direction of where it is going. This approach reduces the number of entries needed in the overall routing table, but at the cost of some flexibility.
Algorithmic routing is used in the Cray T3D. In algorithmic routing, the routing logic is designed for a specific network topology, and calculates the output port based on the current location and destination node number. This approach does not need a routing table but, again, it is limited in flexibility.
What is needed is a more flexible way of using routing tables to route packets across a network.